# 55. 跳跃游戏
# 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
# 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
# 使用贪心算法
def canJump(nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    nums_length = len(nums)
    # 特殊情况考虑
    if nums_length == 1:
        return True
    # 能够到达的最大位置
    max_index = 0

    for index in range(nums_length):
        if nums[index] > 0 and max_index >= index:
            max_index = max(index + nums[index], max_index)

    return max_index >= (nums_length - 1)


# 使用动态规划，
def canJump_dp(nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    nums_length = len(nums)
    # 特殊情况考虑
    if nums_length == 1:
        return True
    # 初始化一维数组
    dp = [False for _ in range(nums_length)]
    dp[0] = nums[0] > 0

    # 给后续的每个位置赋值
    for index in range(nums_length):
        if nums[index] > 0:
            temp = 1
            while temp <= nums[index] and (index + temp) <= (nums_length - 1):
                dp[index + temp] = dp[index]
                temp += 1
    return dp[nums_length - 1]


nums_1 = [4, 2, 1, 0, 1]
result = canJump(nums_1)
print(f'result : {result}')
